package cn.kingshion.stack;

public class LinkedListStackDemo {

    public static void main(String[] args) {
        LinkedListStack linkedListStack = new LinkedListStack();
        System.out.println("入栈前");
        linkedListStack.list();

        System.out.println();
        linkedListStack.push(1);
        linkedListStack.push(2);
        linkedListStack.push(3);
        linkedListStack.push(4);
        linkedListStack.push(5);
        System.out.println("入栈后：");
        linkedListStack.list();

        System.out.println();
        linkedListStack.pop();
        linkedListStack.pop();

        System.out.println("第一次出栈后：");
        linkedListStack.list();
        System.out.println();



        System.out.println("第二层出栈后：");
        linkedListStack.pop();
        linkedListStack.list();



    }
}

class LinkedListStack{
    StackNode head = new StackNode(0);

    //判读链表为空
    public boolean isEmpty(){
        return head.getNext() == null;
    }

    //入栈   入栈时用 int 的数据  但是在内部是用 node 来实现的
    public void push(int value){
        StackNode node = new StackNode(value);
        StackNode temp = head;
        while (true){
            if(temp.getNext()==null){
                break;
            }
            temp = temp.getNext();
        }
        temp.setNext(node);
    }

    //出栈   出栈出的是  int 数据 内部同样是用 node 实现的
    public int pop(){
        if(isEmpty()){
            throw new RuntimeException("栈空，无法出栈！");
        }
        StackNode temp = head;
        StackNode value = null;
        while (true){
            if(temp.getNext().getNext()==null){
                break;
            }
            temp = temp.getNext();
        }
        value = temp.getNext();
        temp.setNext(null);
        return value.getData();
    }

    //打印栈  栈的打印是反向的 先进后出
    // 所以要考虑到这一点就不能单纯的使用链表的遍历 所以反转链表后在对链表进行遍历
    public void list(){
        if (isEmpty()){
            System.out.println("栈空，无法打印！");
            return;
        }
        //原链表反转

        //定义一个辅助节点   用来帮助遍历链表
        StackNode cur = head.getNext();
        //创建一个新的 反转后头结点 临时的用来做一个头结点
        StackNode tempNode = new StackNode(0);
        //定义一个 保存下次遍历开始的节点  因为是单链表，所以如果当前链表断了，后面就丢失了，所以用 next 来保存一下
        StackNode next = null;

        while (cur != null){
            next = cur.getNext();
            cur.setNext(tempNode.getNext());
            tempNode.setNext(cur);
            cur = next;
        }
        head.setNext(tempNode.getNext());

        //重新遍历已经被反转后的链表
        //不再重新定义变量节点，但是记得重新初始化要用的节点
        cur = head.getNext();
        while (cur != null){
            int value = cur.getData();
            System.out.println("栈元素： "+value);
            cur = cur.getNext();
        }
    }


}


/**
 * 创建栈节点
 */
class StackNode{
    private int data;
    private StackNode next;

    public StackNode(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public StackNode getNext() {
        return next;
    }

    public void setNext(StackNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "StackNode{" +
                "data=" + data +
                '}';
    }
}
